package pers.qianyu.month_202012.date_20201229;

import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 23. 合并K个升序链表
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 *
 * @author mizzle rain
 * @date 2020-12-29 20:24
 */
public class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        PriorityQueue<ListNode> q = new PriorityQueue<>((list1, list2) -> list1.val - list2.val);
        for (ListNode list : lists) {
            if (list == null) continue;
            q.offer(list);
        }
        ListNode head = new ListNode(), p = head;
        while (!q.isEmpty()) {
            ListNode node = q.poll();
            p.next = node;
            p = p.next;
            if (node.next != null) {
                q.add(node.next);
            }
        }
        return head.next;
    }
}
